1. Field of the Invention
The present invention relates to schedulers for shared communication links. More specifically, the present invention relates to round robin scheduling of a plurality of clients using a shared resource.
2. Description of Related Art
A scheduler is a basic building block for communication systems that have many users ("clients"), and a limited number of communication links ("shared resources"). For many systems, a scheduler allows multiple clients to share a single data communication resource. The scheduler allocates use of the bus among the competing clients, and it should allocate use as fairly as possible. A client is termed the "master" while it has control of the shared resource. As one example, a bus is a shared resource for a microprocessor. The bus is shared by clients such as a CPU, memory, peripherals, I/O units, modems, etc. and the client who has control of the bus is the master. As another example, communication links between multiple processors are shared resources and the processors themselves are the clients. There may also be multiple communication links that can be treated as clients. Particularly for massively parallel computing, a channel in one of the buses can be treated as a shared resource, and requires scheduling according to the same principles as a single bus.
A number of schemes have been proposed for allocating use of a shared resource. One currently popular scheme is the round robin bus scheduler, which is based on the token ring concept. Conceptually, there are m clients with ordered identities and the clients are offered service one at a time in a predetermined round robin order. A client that requests service therefore waits until it is offered service before beginning transmission. Then, that client becomes the master and begins transmitting. When that client is finished transmitting, the next client in the ring is offered service. If the next client has requested service, then it begins transmitting, otherwise the offer of service moves on to the next client in the ring. Thus, each client in the ring is offered service dependent upon its order in the ring. When the last client is reached, the offer of service loops around to the first client, and then continues from client to client in the predetermined order, looping around each time that it reaches the end.
A round robin scheduler can also be described mathematically. A round robin scheduler has N clients. Let the client that got the resource in the last scheduling cycle be i (1&lt;i&lt;N). The round robin scheduler will find the very first client between i+1 and N that is requesting the resource. If no client in that range is making a request then the scheduler will grant the resource to the first requesting client between 1 and i.
The round robin scheduler has many variations. One of these variations adds the concept of priority to the scheduling decision. For example, several of the clients may have a greater need for the shared resource. In that instance, service may first be offered to those clients having the higher priority before the offer is made to those having a lower priority. An example of such a circuit is disclosed in U.S. Pat. No. 4,375,639, Synchronous Bus Arbiter, issued Mar. 1, 1983 to Johnson, Jr.
Schedulers have been implemented in circuits and software. The amount of time consumed in determining which client will next be granted the shared resource ("the scheduling cycle") is important for some uses such as high speed switching. Schedulers implemented in software generally have a scheduling cycle that is too long for high speed switching of communication lines. Faster scheduling can be accomplished using electrical circuits, and therefore high speed schedulers are generally implemented with electrical circuits.
A scheduler circuit can be implemented with a centralized circuit that receives requests for service and grants a request according to its implemented algorithm. For greater performance in a centrally controlled round robin scheduler, the scheduling cycle can be hidden behind the data communication period. In other words, while the scheduler is performing the scheduling cycle, data is being transmitted according to the grant of the previous scheduling cycle. To obtain maximum benefit from "hiding" the scheduling cycle, the data communication period should be at least as long as the scheduling period. This minimum data communication period may require a larger packet size than would be otherwise desirable for high speed communications.
It would be an advantage to provide a scheduler that has a very short cycle for scheduling access to a shared resource. Such a scheduler could improve the overall performance of any communication system that schedules use of a limited resource among a plurality of clients. Such a scheduler would have particular application for improving the performance of computer data communication within a processor, between a processor and its peripherals, and between multiple processors. It would be a further advantage if the scheduler could be implemented with a simple circuit, and could schedule a large number of clients. Such a scheduler circuit could be manufactured with minimal space requirements on a computer chip at low cost.